Overview |
Topics |
|
Trees are recursive data structures where movement takes place in two dimensions. Unlike linked lists, where only forward and backward movements are allowed, trees allow left and right movements as well. In general a tree is simply a hierarchical collection of nodes. A node is a container used to store left and right pointers to other nodes and some type of data. The first node inserted in a tree is referred to as the root node. The root node always resides at the top of the tree. A pointer to the root node is maintained by the tree algorithm and may change due to the insertion or deletion of other nodes.
All trees start at the root node and grow downward by linking new nodes to the root node. Each node in a tree can only have one link coming into it and any number of links leaving it. By definition, links always point down the tree and there is no path originating from a node that can return to that node. The node where the link originates is called the parent node. The root node has no parent. Links leaving a parent node point to child nodes. At the bottom of the tree are leaf nodes, which have no children. The maximum number of nodes that must be visited on any path from the root to a leaf is referred to as the height of a tree.
When a new node is inserted, the tree algorithm positions the node in the tree structure by assigning values to the left and right pointers of the node above it (the parent node.) The left or right links from parent node to the node below it (the child node) are set based on the data of the new node. If the node has no parent, the tree algorithm will automatically assume that this is the root node and set its left and right pointers to zero or null. Otherwise the new node is considered to be child of the parent node and the tree algorithm will set the child's left and right pointers to point to nodes below it as needed. If there are no nodes below the child, the new node is considered to be a leaf node. The left and right pointers of the leaf node will be made null by the tree algorithm.
Tree nodes are sometimes referred to as internal nodes and external nodes. An internal node is a tree node with data and possibly some children. An external node does not exist. It serves as a conceptual placeholder for new nodes to be inserted. Tree algorithms that use external nodes pretend that all null child links point to a location where the node below it would be inserted if it existed.
Binary Search Trees
A binary trees is a restricted class of general trees that use binary nodes (nodes with no more then two children). Binary search trees are a special class of binary trees that store smaller nodes on the left and larger nodes on the right. This principle is applied recursively down the left and right sub-trees. Smaller and larger nodes refer to the comparison method used by the node's data. The node data is usually an object of class that provides overloaded comparison operators to compare its key data members to other objects of that class. The overloaded comparison operators determine if one object is small, larger, or equal to another object of that class.
In a binary search tree, the longest path ever used to search the tree for a node is equal to the height of the tree. Therefore, the efficiency of a tree depends on the number of nodes that must be visited on any path from the root to a leaf. In order to obtain the smallest possible height, the tree must be balanced so both the left and right sub-trees have approximately the same number of nodes. If the tree becomes extremely unbalanced due to numerous insertions and deletions it will be degraded to a linked list. In unbalanced trees each parent node in the tree has one child causing search operations to become linear.
A new node is inserted into the tree by searching the tree to determine if it already exists in the tree. If the node does not exist in the tree, a new node will be allocated and inserted in the location where it would have been if the search had been successful finding it. The link to the new node is stored in left or right pointer of its parent node accordingly.
Deleting a node requires checking to see if the node is a leaf, if it has only one child, or if it has two children. If the node is a leaf it can simply be deleted and the corresponding child pointer of its parent set to null. If the node has only one child, the single child can be promoted up the tree to take the place of the deleted node. If the node has two children, another node must be found to take the place of the one deleted and still maintain binary search tree properties. In this case the predecessor or the successor of the node is used to take the place of the deleted node. Both the predecessor and successor nodes are guaranteed to have no more than one child, and that child can have none. The predecessor of a node is found by going down the left once, and then all the way to the right as far as possible. The successor of the node is found by going down the right once and then all the way to the left as far as possible. When deleting all the nodes in a tree, always start from the bottom and work up the tree.
Red Black Trees
The red-black tree algorithm is a method for maintaining balanced binary search trees. By coloring each node in the tree either red or black and then manipulating the tree during node insertion and deletion operations the balance of the structure is preserved. A red-black tree is a binary representation of a B-tree. It maintains binary search tree properties, by allowing nodes to have no more then two children, but it ensures the tree will be balanced by assigning the links between nodes the colors red and black. A black parent link is referred to as a black node and a red parent link is referred to as a red node. The link colors serve as a guide in determining what kind of rotations to do when balancing the tree.
The number of black nodes on any path from the root node to a leaf node is referred to as the black-height of the tree. The black-depth of a node is the number of black nodes found on the path from the root to that node. All external nodes have a black-depth of two. These properties guarantee that any link from the root to a leaf is no more than twice as long of any other. The largest path that can ever be constructed is twice the length of the shortest path in the tree (a path containing only black nodes.) All insert and delete operations must maintain the properties listed above.
The color in red-black trees can be mapped three different ways. One, mapped as single binary nodes with two black children. Two, mapped as pairs of binary nodes with one red and one black node having a red link between the nodes. Three, mapped as sets of three binary nodes with black parent nodes and red child nodes. The colors of the nodes are not used when searching a red-black tree. Search operations in a red black tree are performed the exact same way they are in binary search trees. However, searching a red black tree is faster because the tree is balanced keeping the height of the tree smaller.
Inserting nodes into a red-black tree involves a two-pass operation. A top-down pass determines where the new node should go, and a bottom-up pass handles any nodes with two children that need to split in order to maintain balance. It is possible to perform single-pass top-down insertions with a color flip operation. Every time a black node with two red children is encountered, the parent node is colored red and the two children are colored black. When the bottom of the tree is reached and the node to be inserted is not found, a new node is added and colored red. Color flips do not change the black-height of the tree and help ensure easier insertions in most cases. However, color flips can produce two red nodes in a row, which is not allowed. In order to eliminate pairs of consecutive red nodes, a tree rotation must be performed. A tree rotation is performed in a series of steps. One, by making the current node's right child equal to the current node's right child's left child. Two, by making the current node's right child's parent the current node's parent. Three, by making the current node's right child's left child the current node. During a tree rotation the tree algorithm may have to reorder the tree by prompting or demoting the current node, its parent, its grandparent, or the left or right siblings of the effected nodes. Promoting a node moves it further up the tree by adjusting the left and right pointers of the nodes above it and below it and the root pointer if necessary. Demoting a node moves it further down the tree. Several color changes may also take place during a tree rotation.
Deleting nodes from a red-black tree works almost the same way as deleting nodes from a regular binary search tree. Basically the node data in that node's successor is swapped with the node data of the node to be deleted. Then the successor node with no data is deleted. This works with no further complications if the successor is red. If the successor is black and removed from the tree, then all the nodes under the successor will have their black depth reduced by one. This results in an illegal red-black tree. One way to avoid this situation is to ensure that a node's successor is always red by pushing an extra red down the tree towards the successor. When the node to be deleted is reached its successor is guaranteed to be red. The following rotations and color flips are used to push an extra red node down the tree. One, by merging single binary nodes with two black children into a set of three binary nodes with black parent nodes and red child nodes (just the opposite of the color flip used during insertions.) Two, by flipping the red-black orientations of a pair of binary nodes (one black, one red.) Three, by rotating a pair of binary nodes (one black, one red) and a set of three binary nodes (with black parent nodes and red child nodes) from one side of the tree to the other. The rotations always take place toward the side containing the current node being visited.
Tree Traversals
A tree traversal is a method of visiting every node in the tree and performing some type of operation. The binary tree classes presented here uses four basic traversals.
The first three traversal algorithms are recursive in nature. They must walk down the tree and then back up. Since the links of a tree only go downward, a pointer to each parent visited must be saved in order to go back up the tree. To do this, parent node pointers are pushed into a stack while traveling down the tree and popped from the stack to travel up the tree.
Recursive functions use the implicit processor stack to store its parent nodes, unless an explicit stack is implemented. The amount of stack space used is determined by the height of the tree. For a tree of height n, n parent nodes are placed on the stack making the recursive call up to n levels deep. In functions where no statements follow the last recursive call, tail recursion occurs. In a tail-recursive call, the function's local variables are saved on the processor even though they are no longer needed because nothing follows the recursive call. The binary tree recursive functions presented here eliminate tail recursion whenever possible.
In recursive calls, the parent node pointer, a visit function pointer, and the return address are all saved on the processor stack. NOTE: A visit function pointer refers to a function pointer that points to a visit action defined in the application. The visit action defines a procedure used to process the node data. An explicit stack can be used to flatten out recursion by only storing the node pointers. The binary tree functions presented here use the Stack class and the Queue class to create explicit stacks that flatten out recursion and turn it into an iteration. Tree operations that manage more variables then just the nodes themselves do not use an explicit stack because the state of the variables are already saved on some type of stack.
The BNodeBase is a base class for all the binary tree node classes. It serves as a container for the nodes and does not store any tree data. This implementation separates the nodes from the data stored in the tree to form a heterogeneous container capable of handling any type of node data. Functions that take BNodeBase pointers as parameters can be shared across all binary trees regardless of the data type stored in the tree nodes.
class BNodeBase
{
public:
BNodeBase *Left;
BNodeBase *Right;
};
The generic BNode class is derived from the BNodeBase base class. Only a template version of the BNode class is implemented. If your application cannot use templates, code this class directly for the data type being used. Templates were used to allow the binary tree classes to handle numerous data types without having to provide a different version for each data type used.
template<class TYPE>
class BNode : public BNodeBase
{
public:
BNode() { Left = 0; Right = 0; }
BNode(const TYPE &X, BNode<TYPE> *L=0, BNode<TYPE> *R=0) : Data(X) {
Left = L; Right = R; }
public:
BNode<TYPE> *GetLeft() { return (BNode<TYPE> *)Left; }
BNode<TYPE> *GetRight() { return (BNode<TYPE> *)Right; }
public:
TYPE Data;
};
The base to derived typecast in the BNode::GetLeft() and BNode::GetRight() functions are needed to cast the BNode pointers to BNode<TYPE> pointers.
STANDALONE FUNCTIONS:
The following functions are not part of the BNodeBase class. They operate on BNodeBase pointers as standalone functions. This implementation provides maximum code sharing allowing this code to work for all binary trees.
BNodeBase *RotateRight(BNodeBase *ptr) - Rotates to the right around the non-null pointer ptr. This function assumes a left child of pointer ptr exists. Returns a pointer to the node that takes the place of pointer ptr.
BNodeBase *RotateLeft(BNodeBase *ptr) - Rotates to the left around the non-null pointer ptr. This function assumes a right child of pointer ptr exists. Returns a pointer to the node that takes the place of pointer ptr.
int NumNodes(BNodeBase *Tree) - Recursive function used to count the number of nodes in the tree, using pre-order traversal with tail recursion eliminated.
int Height(BNodeBase *Tree) - Recursive function used to determine the height of the tree. The height of a tree is the maximum height of its two sub-trees.
void PreOrder(BNodeBase *Tree, VisitFunc Visit) - Recursive function used to visit each node in the tree using pre-order traversal (parent, left sub-tree, then the right sub-tree) with tail recursion eliminated. The VisitFunc function pointer refers to a function pointer that points to a visit action. A visit action defines a procedure used to process the node data.
void InOrder(BNodeBase *Tree, VisitFunc Visit) - Recursive function used to visit each node in the tree using in-order traversal, (left sub-tree, parent, then the right sub-tree) with tail recursion eliminated. The VisitFunc function pointer refers to a function pointer that points to a visit action. A visit action defines a procedure used to process the node data.
void PostOrder(BNodeBase *Tree, VisitFunc Visit) - Recursive function used to visit each node in the tree using post-order traversal (left sub-tree, right sub-tree, then the parent). The VisitFunc function pointer refers to a function pointer that points to a visit action. A visit action defines a procedure used to process the node data.
void LvlOrder(BNodeBase *Tree, VisitFunc Visit) - Non-recursive function used to visit each node in the tree from top to bottom, left to right, level by level. This uses the Queue class to maintain a queue of nodes. Nodes are pulled of the queue one at a time, visited, and then the children of the nodes are inserted onto the end of the queue. The VisitFunc function pointer refers to a function pointer that points to a visit action. A visit action defines a procedure used to process the node data.
void PreOrderFlat(BNodeBase *Tree, VisitFunc Visit) - Recursive function used to visit each node in the tree using pre-order traversal (parent, left sub-tree, then the right sub-tree), using an explicit stack. The VisitFunc function pointer refers to a function pointer that points to a visit action. A visit action defines a procedure used to process the node data.
void InOrderFlat(BNodeBase *Tree, VisitFunc Visit) - Recursive function used to visit each node in the tree using in-order traversal (left sub-tree, parent, then the right sub-tree), using an explicit stack.
void PostOrderFlat(BNodeBase *Tree, VisitFunc Visit) - Recursive function used to visit each node in the tree using post-order traversal (left sub-tree, right sub-tree, then the parent), using an explicit stack. The VisitFunc function pointer refers to a function pointer that points to a visit action. A visit action defines a procedure used to process the node data.
The TreeWalkerb base class defines a generic iterator used to visit every node in a binary tree using a specified walk order: PREORDER, POSTORDER, INORDER, or LVLORDER.
TreeWalkerb::TreeWalkerb(BNodeBase *r, WalkOrder w) - Class constructor responsible for setting a pointer to the root node and setting the walk order. WalkOrder is an enumeration used to specify PREORDER, POSTORDER, INORDER, or LVLORDER traversal.
virtual TreeWalkerb::~TreeWalkerb() - Class destructor provided for virtuality.
void TreeWalkerb::Reset() - Public member function used to reset this object's root node pointer and walk order.
void TreeWalkerb::Reset(BNodeBase *r, WalkOrder w) - Public member function used to set this object's root node pointer and walk order. WalkOrder is an enumeration used to specify PREORDER, POSTORDER, INORDER, or LVLORDER traversal. This function is responsible for initializing the NextFptr member function pointer by giving it the address of a traversal function: TreeWalkerb::NextPreOrder(), TreeWalkerb::NextInOrder(), TreeWalkerb::NextPostOrder(), or TreeWalkerb::NextLvlOrder(). These member functions do not have access to the stack stored in the iterator object. They use an explicit stack to store node pointers when walking up and down the tree and do not process the node data when visiting. Instead of making a call to a pre-defined visit function, these functions return a pointer to the node visited.
BNodeBase *TreeWalkerb::Next() - Public member function that returns a pointer to the next node in sequence. This function makes a call to the one of the traversal functions pointed to by the NextFptr member function pointer.
BNodeBase *(TreeWalkerb::* NextFptr)() - Pointer to one of the tree transversal functions: TreeWalkerb::NextPreOrder(), TreeWalkerb::NextInOrder(), TreeWalkerb::NextPostOrder(), or TreeWalkerb::NextLvlOrder(). NOTE: A pointer to non-static member functions must be handled differently than ordinary function pointers. C++ introduces a new type of pointer, called a pointer-to-member, which can be invoked only by providing an object. A pointer-to-member-function is not required to contain the machine address of the appropriate function. It cannot be cast into a pointer-to-function. Non-static member functions have a hidden parameter that corresponds to the this pointer. The this pointer, points to the instance data for the object. In order to invoke the call an object must be specified to make the member function call. The TreeWalkerb::Next() function calls the member function pointer NextFptr using the object in question: return (this->*NextFptr)();
BNodeBase *TreeWalkerb::NextPreOrder() - Protected member function used to visit each node in the tree using pre-order traversal (parent, left sub-tree, then the right sub-tree) using an explicit stack. Returns a pointer to the node to be visited.
BNodeBase *TreeWalkerb::NextInOrder() - Protected member function used to visit each node in the tree using in-order traversal (left sub-tree, parent, then the right sub-tree), using an explicit stack. Returns a pointer to the node to be visited.
BNodeBase *TreeWalkerb::NextPostOrder() - Protected member function used to visit each node in the tree using post order traversal (left sub-tree, right sub-tree, then the parent), using an explicit stack. Returns a pointer to the node to be visited.
BNodeBase *TreeWalkerb::NextLvlOrder() - Protected member function used to visit each node in the tree from top to bottom, left to right, level by level. Returns a pointer to the node to be visited.
The TreeWalker class is derived from the TreeWalkerb base class. It is used to construct a generic iterator object used to visit every node in a binary tree using a specified walk order: PREORDER, POSTORDER, INORDER, or LVLORDER. Only a template version of the TreeWalker class is implemented. If your application cannot use templates, code this class directly for the data type being used. Templates were used to allow the binary tree classes to handle numerous data types without having to provide a different version for each data type used.
template<class NTYPE>
class TreeWalker : private TreeWalkerb
{
public:
TreeWalker(NTYPE *r, WalkOrder w) : TreeWalkerb(r, w) { }
public:
void Reset() { TreeWalkerb::Reset(); }
void Reset(NTYPE *r, WalkOrder w) { TreeWalkerb::Reset(r, w); }
NTYPE *Next() { return (NTYPE *)((this-*NextFptr)()); }
};
The generic binary search tree class is used to implement basic binary tree operations. Only a template version of the BSTree class is implemented. If your application cannot use templates, code this class directly for the data type being used. Templates were used to allow the binary tree classes to handle numerous data types without having to provide a different version for each data type used.
BSTree<TYPE>::BSTree() - Class constructor responsible for initializing the root pointer.
virtual ~BSTree<TYPE>::BSTree() - Virtual call destructor responsible for clearing the tree.
BSTree<TYPE>::BSTree(const BSTree<TYPE> &t) - Class copy constructor used to copy construct tree t.
void BSTree<TYPE>::operator=(const BSTree<TYPE> &t) - Class assignment operator used to assign tree t to the object that invoked the call. This assignment operator does not allow chained assignment.
int BSTree<TYPE>::Copy(const BSTree<TYPE> &Tree - Public member function used to copy the contents of tree t into the object the invoked the call.
int BSTree<TYPE>::Copy(const BSTree<TYPE> &Tree, WalkOrder w) - Public member function used to copy the contents of tree t into the object the invoked the call using the specified tree traversal. WalkOrder is an enumeration used to specify PREORDER, POSTORDER, INORDER, or LVLORDER traversal.
void BSTree<TYPE>::Clear() - Public member function used to clear the tree.
BNode<TYPE> *BSTree<TYPE>::GetMember(const TYPE &X) - Public member function that returns a pointer to the node containing data X.
BNode<TYPE> *BSTree<TYPE>::Add(const TYPE &X, int &existed) - Public member function used to add a node to the tree. This function will search the tree for the node before adding it. If a node pointing to data X already exists in the tree the existed variable will be set to one.
BNode<TYPE> *BSTree<TYPE>::Add(const TYPE &X) - Public member function used to add a node to the tree. This function will search the tree for a node pointing to data X before adding the new node.
BNode<TYPE> *BSTree<TYPE>::Detach(const TYPE &X) - Public member function used to detach the node pointing to data X from the tree. This function searches the tree for the node pointing to data X and then calls the standalone DetachNode() function to determine which node to detach.
BNode<TYPE> *BSTree<TYPE>::DetachMin() - Public member function used to detach the smallest node in the tree (the node all the way to the left.)
BNode<TYPE> *BSTree<TYPE>::DetachMax() - Public member function used to detach the largest node in the tree (the node all the way to the right.)
int BSTree<TYPE>::Delete(const TYPE &X) - Public member function used to delete the node pointing to data X if it exists. This function calls the BSTree::Detach() to determine which node to detach.
void BSTree<TYPE>::DeleteMin() - Public member function used to delete the smallest node in the tree (the node all the way to the left.) This function calls the BSTree::DetachMin() to determine which node to detach.
void BSTree<TYPE>::DeleteMax() - Public member function used to delete the largest node in the tree (the node all the way to the right.) This function calls the BSTree::DetachMax() to determine which node to detach.
BNode<TYPE> *BSTree<TYPE>::GetRoot() - Public member that returns a pointer to the root node.
BNode<TYPE> *BSTree<TYPE>::GetMin() - Public member function that returns a pointer to the smallest node in the tree (the node all the way to the left.)
BNode<TYPE> *BSTree<TYPE>::GetMax() - Public member function that returns a pointer to largest node in the tree (the node all the way to the right.)
int BSTree<TYPE>::IsEmpty() const - Public member function that returns true if the tree is empty, meaning that the root pointer equals zero.
BNode<TYPE> *BSTree<TYPE>::SearchP(const TYPE &X, BNode<TYPE> *&p, int &Side) - Protected member function that returns the parent of the matching node pointing to data X, as well as the node itself. Each node to the left is smaller then the given node, and each node to right is larger. The side variable is set to zero if the node is on the left or one if the node is on the right. Pointer p is used to pass back the pointer to the parent node.
BNode<TYPE> *BSTree<TYPE>::DupTree(BNode<TYPE> *Tree) - Protected member function that recursively duplicates an entire tree using post-order traversal.
virtual void BSTree<TYPE>::FreeNode(BNode<TYPE> *n) - Virtual protected member function used to delete a node.
void BSTree<TYPE>::DelTree(BNode<TYPE> *Tree) - Protected member function used to recursively delete an entire tree from the bottom up.
virtual BNode<TYPE> *BSTree<TYPE>::AllocNode(const TYPE &X, BNode<TYPE> *L=0, BNode<TYPE> *R=0) - Virtual protected member function used to allocate memory for a node. Each tree node stores a pointer to data X, a pointer to the sub-tree on the left, and a pointer to the sub-tree on the right.
STANDALONE FUNCTIONS:
The following are standalone functions that operate on BNodeBase pointers and are used in conjunction the BSTree class. This implementation provides maximum code sharing for the generic BSTree class, allowing this code to be shared by all binary search trees regardless of the type of data they hold.
BNodeBase *Minimum(BNodeBase *Tree) - Standalone function that returns the smallest node in the tree, which is found by going as far left as possible. If Tree is a null value, a null is returned, else a pointer to the minimum node is returned.
BNodeBase *Maximum(BNodeBase *Tree) - Standalone function that returns the largest node in the tree, which is found by going as far right as possible. If Tree is a null value, a null is returned, else a pointer to the maximum node is returned.
BNodeBase *ParentOfMinimum(BNodeBase *Tree) - Standalone function that returns a pointer to the parent of the smallest node in the tree, which is found by going as far left as possible. If Tree is a null value or is itself the minimum, a null is returned.
BNodeBase *ParentOfMaximum(BNodeBase *Tree) - Standalone function that returns a pointer to the parent of the largest node in the tree, which is found by going as far right as possible. If Tree is a null value, or is itself the minimum, a null is returned.
BNodeBase *ParentOfPredecessor(BNodeBase *Tree) - Standalone function that returns the node's parent of its predecessor, which is found by going left once and then all the way to the right. The predecessor of the node's right child is returned, unless the node itself is a parent. If this node is a parent then the left child of this node is the predecessor. If the node is a leaf, zero is returned. This function assumes the tree is not empty.
BNodeBase *ParentOfSuccessor(BNodeBase *Tree) - Standalone function that returns the node's parent of its successor, which is found by going right once and then all the way to the left. The successor of the node's left child is returned, unless the node itself is a parent. If this node is a parent then the right child of this node is the successor. If the node is a leaf, zero is returned. This function assumes the tree is not empty.
BNodeBase *DetachNode (BNodeBase *&root, BNodeBase *Tree, BNodeBase *p, int Side) - Standalone function used to determine which node with parent p to detach from the tree before the node can be removed. The node is the left child if the Side variable equals zero or right child if the Side variable equals one. If parent p is zero, it means the node is the root, and that is handled accordingly. Redundantly returns the pointer to the node and will update root pointer if necessary.
The RBNodeBase class is derived from the BNodeBase class. It serves as a base class for the generic RBNode class and adds a data member used to represent the red and black links in the tree. This implementation separates the nodes from the data store in the tree to from a heterogeneous container capable of handling any type of node data.
class RBNodeBase : public BNodeBase
{
public:
// These functions return references to the Left and Right pointers
RBNodeBase *GetLeft() { return (RBNodeBase *)Left; }
RBNodeBase *GetRight() { return (RBNodeBase *)Right; }
public:
char color; // Color of the link coming into the node
};
The generic RBNode class is derived from the RBNodeBase class. Only a template version of the RBNode class is implemented. If your application cannot use templates, code this class directly for the data type being used. Templates were used to allow the red-black tree classes to handle numerous data types without having to provide a different version for each data type used.
template<class TYPE>
class RBNode : public RBNodeBase
{
public:
RBNode() { Left = 0; Right = 0; color = BlackNode; }
RBNode // RBNode copy constructor
(const TYPE &X, char c=1, RBNode<TYPE> *l=0, RBNode<TYPE> *r=0) : Data(X)
{
Left = l; Right = r; color = c;
}
public:
RBNode<TYPE> *GetLeft() { return (RBNode<TYPE> *)Left; }
RBNode<TYPE> *GetRight() { return (RBNode<TYPE> *)Right; }
public:
TYPE Data;
};
The generic red-black tree class is used to implement all the red-tree tree operations. Only a template version of the RBTree class is implemented. If your application cannot use templates, code this class directly for the data type being used. Templates were used to allow the red-black tree classes to handle numerous data types without having to provide a different version for each data type used.
RBTree<TYPE>::RBTree() - Class constructor responsible for initializing the root pointer.
virtual RBTree<TYPE>::~RBTree() - Virtual call destructor responsible for clearing the tree.
RBTree<TYPE>::RBTree(const RBTree<TYPE> &t) - Class copy constructor used to copy construct tree t.
void RBTree<TYPE>::operator=(const RBTree<TYPE> &t) - Class assignment operator used to assign tree t to the object that invoked the call. This assignment operator does not allow chained assignment.
int RBTree<TYPE>::Copy(const RBTree<TYPE>&t) - Public member function used to copy the contents of tree t into the object that invoked the call.
int RBTree<TYPE>::Copy(const RBTree<TYPE> &t, WalkOrder w) - Public member function used to copy the contents of tree t into the object that invoked the call using the specified tree traversal. WalkOrder is an enumeration used to specify PREORDER, POSTORDER, INORDER, or LVLORDER traversal.
void RBTree<TYPE>::Clear() - Public member function used to clear the tree.
RBNode<TYPE> *RBTree<TYPE>::GetMember(const TYPE &X) - Public member function that returns a pointer to the node containing data X.
const RBNode<TYPE> *RBTree<TYPE>::GetMember(const TYPE &X) - Public member function that returns a pointer to the node containing data X.
RBNode<TYPE> *RBTree<TYPE>::Add(const TYPE &X, int &existed) - Public member function used to add a node to the tree. This function will search the tree for the node before adding it and may cause the tree to re-constructed even if the node exists. If a node pointing to data X already exists in the tree the existed variable will be set to one. The standalone InsBalance() function is called to balance the tree if two red links in a row occur during the insertion. Returns a pointer to the node containing data X.
RBNode<TYPE> *RBTree<TYPE>::Add(const TYPE &X) - Public member function used to add a node to the tree. This function will search the tree for a node pointing to data X before adding the new node and may cause the tree to re-constructed even if the node exists. The standalone InsBalance() function is called to balance the tree if two red links in a row occur during the insertion. Returns a pointer to the node containing data X.
RBNode<TYPE> *RBTree<TYPE>::Detach(const TYPE &X) - Public member function used to detach the node pointing to data X from the tree. This function walks the tree from the top down, searching for the node to delete, recording its location, and then continuing to walk the tree pretending that the node was not found. When a null node is reached, the current parent will be the successor node. Rotations and color flips are done by calling the standalone DelBalance() function. At the end, the standalone DoReplacement() function is called to swap the node data in that node's successor with the node data of the node to be deleted. Then the successor node with no data is deleted.
RBNode<TYPE> *RBTree<TYPE>::DetachMin() - Public member function used to detach the smallest node in the tree (the node all the way to the left.)
RBNode<TYPE> *RBTree<TYPE>::DetachMax() - Public member function used to detach the largest node in the tree (the node all the way to the right.)
int RBTree<TYPE>::Delete(const TYPE &X) - Public member function used to delete the node pointing to data X if it exists. This function calls the RBTree::Detach() function to determine which node to detach and then frees the node.
void RBTree<TYPE>::DeleteMin() - Public member function used to delete the smallest node in the tree (the node all the way to the left.)
void RBTree<TYPE>::DeleteMax() - Public member function used to delete the largest node in the tree (the node all the way to the right.)
RBNode<TYPE> *RBTree<TYPE>::GetRoot() - Public member that returns a pointer to the root node.
RBNode<TYPE> *RBTree<TYPE>::GetMin() - Public member function that returns a pointer to the smallest node in the tree (the node all the way to the left.)
RBNode<TYPE> *RBTree<TYPE>::GetMax() - Public member function that returns a pointer to largest node in the tree (the node all the way to the right.)
int RBTree<TYPE>::IsEmpty() const - Public member function that returns true if the tree is empty, meaning that the root pointer equals zero.
virtual RBNode<TYPE> *RBTree<TYPE>::AllocNode(const TYPE &X, char c=1, RBNode<TYPE> *l=0, RBNode<TYPE> *r=0) - Virtual protected member function used to allocate memory for a node. Each tree node stores a pointer to data X, a pointer to the sub-tree on the left, a pointer to the sub-tree on the right, and the appropriate color of the link (red or black.)
RBNode<TYPE> *RBTree<TYPE>::DupTree(RBNode<TYPE> *t) - Protected member function that recursively duplicates an entire tree using post-order traversal.
void RBTree<TYPE>::FreeNode(RBNode<TYPE> *n) - Virtual protected member function used to delete a node after it has been detached from the tree.
void RBTree<TYPE>::DelTree(RBNode<TYPE> *t) - Virtual protected member function used to allocate memory for a node. Each tree node stores a pointer to data X, a pointer to the sub-tree on the left, and a pointer to the sub-tree on the right.
STANDALONE FUNCTIONS:
The following are standalone functions that operate on RBNodeBase pointers and are used in conjunction the RBTree class. This implementation provides maximum code sharing for the generic RBTree class, allowing this code to be shared by all red-black trees regardless of the type of data they hold. Pointers to the current node, its parent, grandparent, great grandparent, sibling, and its sibling's right and left children are packaged in a structure and passed via a pointer during tree rotations as a convenient way to keep track of all the necessary pointers effected by the rotation.
RBNodeBase *InsBalance(RBNodeBase *Root, PtrPack &pp) - Standalone function used for balance adjustments during single-pass top-down insertions. This function eliminates both the parent and the current node from being red by doing rotations and color flips. The grandparent, parent, and the current node are assumed that they are not null coming in. The great grandparent may be a null value. At the end of this routine, only the current node and the parent will be valid with respect to each other. The grandparent and the great grandparent may not reflect the proper ordering.
RBNodeBase *DelBalance(RBNodeBase *Root, PtrPack &pp) - Standalone function used for balancing adjustments during a top-down deletion. This function is responsible for the tree rotations and color flips needed while walking down the tree searching for the node to delete.
RBNodeBase *DoReplacement(RBNodeBase *Root, PtrPack &pp) - Standalone function used for swapping the node data in the matching node's successor with the node data of the matching node to be deleted. Then the successor node with no data is deleted. If the matching node has no successor the parent node will equal the matching node and the replacement node becomes the non-null child of the matching node.
RBNodeBase *DetachMinMax(RBNodeBase *&Root, int mx) - Standalone function used to detach the smallest node in the tree (the node all the way to the left) or the largest node in the tree (the node all the way to the right) if the mx variable is true.